package offer;

/**
 * 描述:
 *
 * @author Madison You
 * @created 23:54
 */
public class Mid_26_IsSubStructure {

    public static void main(String[] args) {
        TreeNode treeNode1 = CreateTreeNode.arrayToTreeNode(new Integer[]{3, 4, 5, 1, 2});
        TreeNode treeNode2 = CreateTreeNode.arrayToTreeNode(new Integer[]{4,2});
        new Mid_26_IsSubStructure().isSubStructure(treeNode1, treeNode2);
    }

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    private boolean dfs(TreeNode A, TreeNode B) {
        if (A == null) return false;
        if (B == null) return true;
        return A.val == B.val && dfs(A.left, B.left) && dfs(A.right, B.right);
    }

}
